/*
LRU是Least Recently Used的缩写，译为最近最少使用。它的理论基础为 “最近使用的数据会在未来一段时期内仍然被使用，已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”
由于该思想非常契合业务场景 ，并且可以解决很多实际开发中的问题，所以我们经常通过LRU的思想来作缓存，一般也将其称为LRU缓存机制。

思考：有没有考虑过LRU算法实现中为什么使用map，它的好处是什么？对于LRU算法，是get使用频率更高还是put使用频率更高？为什么？LRU算法的使用场景？
    一：使用map，它的好处是什么?:
    1. 时间复杂度：使用 map 可以从 O(n) 降到 O(1)，因为 map 在查找是否存在某个键值对的时候，可以通过对键进行哈希运算，快速定位到哈希表中的位置，从而实现快速查找。
    2. 空间复杂度：使用 map 可以节省空间，因为 LRU 算法需要一个能够快速插入和删除元素的容器，而 map 内部采用红黑树实现，可以高效地完成插入、删除等操作。
    3. 易于实现：使用 map 可以简化 LRU 算法的实现，因为 map 自带了许多功能，例如插入、删除、查找等，可以减少代码量和工作量。
    二：对于LRU算法，是get使用频率更高还是put使用频率更高？为什么？:
    在 LRU（最近最少使用）算法中，get 操作可能更频繁使用，因为它用于获取缓存中存储的元素，如果缓存中存在需要的数据，那么就可以直接返回，从而避免了对底层存储介质的访问，因此会更加快速和高效。
    相比之下，put 操作可能较少使用，因为它用于将新的数据存储到缓存中，如果缓存已满，则需要先淘汰掉最近最少使用的元素，从而为新的数据腾出空间，这个操作需要额外的时间和计算资源，因此相对来说 put 操作的使用频率可能会稍微低一些。
    三：LRU算法的使用场景？
    1. Web 缓存：用于缓存最近的 Web 页面，从而避免重复的网络请求和数据传输，提高 Web 页面的加载速度。
    2. 数据库引擎：用于缓存经常访问的数据页，从而减少磁盘 IO 操作，提高数据库系统的响应能力和性能。
    3. 操作系统页缓存：用于缓存最近访问的文件页，提高操作系统的磁盘 IO 性能。
    4. 图像处理：用于缓存最近使用的图像数据，提高图像处理的性能和响应速度。
    5. 电子商务：用于缓存最近访问的商品数据，从而加快网站的加载速度和响应时间。
    总之，任何需要对访问模式进行优化的场景都可能会使用到 LRU 算法，从而提高数据访问的效率和性能。
    四:使用map来实现LRU算法在delete时的时间复杂度为O(n),这是可以优化的点
    https://github.com/Sunny-117/js-challenges/issues/272
 */
// 传统map设计LRU缓存结构
class LRUCache6 {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        // 没有则返回-1
        if (!this.cache.has(key)) {
            return -1;
        }
        // 有则删除再添加(即更新其最近使用时间)
        let value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
    }

    put(key, value) {
        //如果有 就删了再赋值(即更新其最近使用时间)
        if (this.cache.has(key)) {
            this.cache.delete(key);
        }
        // 如果容量满了
        if (this.cache.size >= this.capacity) {
            // 获取第一个key的值(map.keys()返回的是一个迭代器对象故可以使用next())
            let key = this.cache.keys().next().value;
            this.cache.delete(key);
        }
        this.cache.set(key, value);
    }

    toString() {
        console.log('capacity', this.capacity);
        console.table(this.cache);
    }
}
//
// const lruCache6 = new LRUCache6(2);
// lruCache6.put(1, 'first');
// lruCache6.put(2, 'second');
// lruCache6.get(1);
// lruCache6.toString()
// lruCache6.put(3, 'third');
// lruCache6.toString();
/*
 最佳方案应该是用Map+双向链表的方式来求解
 考虑到在链表中执行 put 操作和delete 操作需要知道待插入节点的前驱节点和后继节点，如果使用单向链表的话，需要进行一次遍历，才能找到前驱和后继，这样就违背了O(1)时间复杂度的初衷，
 因此，我们应采用双向链表的方式来标记每个节点的信息，这样就可以通过prev指针很方便的找到前驱节点，通过next指针很方便的找到后继节点啦
 */
// 定义一下双向链表中每个节点所拥有的属性
const linkListNode = function (key = "", val = "") {
    this.val = val;
    this.key = key;
    this.pre = null;
    this.next = null;
}

// 设置链表初始状态下节点及它们之间的指向，（生成头节点和尾结点）
// head -> tail
//      <-
const linkList = function () {
    let head = new linkListNode("head", "head");
    let tail = new linkListNode("tail", "tail");
    head.next = tail;
    tail.pre = head;
    this.head = head;
    this.tail = tail;
}

// 链表头节点添加，每次有新元素的时候就添加在头节点处，因此链表元素越靠前，说明元素等级越高
linkList.prototype.append = function (node) {
    node.next = this.head.next;
    node.pre = this.head;
    this.head.next.pre = node;
    this.head.next = node;
}

// 链表删除指定节点
linkList.prototype.delete = function (node) {
    console.log('laiel1')
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

// 删除并返回链表的最后一个节点（非tail）
// 取到链表的最后一个节点（非tail节点），删除该节点并返回节点信息
linkList.prototype.pop = function () {
    // 非tail 所以指向tail的pre
    let node = this.tail.pre;
    node.pre.next = this.tail;
    this.tail.pre = node.pre;
    // 返回其信息
    return node;
}

// 打印链表信息
// 将链表的信息按顺序打印出来，入参为需要打印的属性
linkList.prototype.linkConsole = function (key = 'val') {
    let h = this.head;
    let res = "";
    while (h) {
        if (res != "") {
            res += "-->";
            res += h[key];
            h = h.next;
        }
    }
    console.log(res);
}

// LRUCache数据结构
// capacity保存最大容量，kvMap保存节点信息，linkList为节点的顺序链表
const LRUCache = function (capacity) {
    this.capacity = capacity;
    this.kvMap = new Map();
    this.linkList = new linkList();
}

// put方法
// 如果关键字key已经存在，则变更其数据值value，并重置节点链表顺序，将该节点移到头节点之后；如果不存在，则向缓存中插入该组key-value。
// 如果插入操作导致关键字数量超过capacity，则应该踢掉最久未使用的关键字。
LRUCache.prototype.put = function (key, value) {
    if (this.kvMap.has(key)) {
        // 踢掉再加 更新时间(只动影响顺序的链表)
        let node = this.kvMap.get(key);
        node.val = value;
        this.linkList.delete(node);
        this.linkList.append(node);
    } else {
        // 直接往链表插咯
        let node = new linkListNode(key, value);
        // 如果Map容量满了 删最后一个元素
        if (this.capacity === this.kvMap.size) {
            let nodeP = this.linkList.pop();
            this.kvMap.delete(nodeP.key);
        }
        this.kvMap.set(key, node);
        this.linkList.append(node);
    }
}

// get方法
// 如果关键字key存在于缓存中，则返回关键字的值，并重置节点链表顺序，将该节点移到头结点之后，否则，返回-1
LRUCache.prototype.get = function (key) {
    // 没有 则-1
    if (!this.kvMap.has(key)) {
        return -1;
    }
    // 有 也是先删后加(链表中先删后加 因为链表存顺序而map只存哪些元素)
    let node = this.kvMap.get(key);
    this.linkList.delete(node);
    this.linkList.append(node);
    return node.val;
}
const obj = new LRUCache(2);
obj.put(1, 1);// 1
obj.put(2, 2);// 2 -> 1
console.log(obj.get(1)); // 1 -> 2
obj.put(3, 3);// 3 -> 1
console.log(obj.get(2));// 此时缓存里没有2的位置了，因此会返回-1
obj.put(4, 4);// 4 -> 3
console.log(obj.get(1));// 此时缓存里没有1的位置了，因此会返回-1
console.log(obj.get(3));// 3 -> 4
console.log(obj.get(4));// 4 -> 3
